Гра в Морський бій з комп`ютером

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

ЗМІСТ

Введення

1 Постановка завдання

2 Математичні та алгоритмічні основи рішення задачі

3 Функціональні моделі та блок-схеми виконання завдання

4 Програмна реалізація рішення задачі

5 Приклад виконання програми

Висновок

Список використаних джерел та літератури

Введення

Гра «морський бій» досить добре відома і популярна. Практично кожен школяр у той чи інший період свого життя грав у цю гру. В останні роки у зв'язку з появою комп'ютерів і нових навчальних і розвиваючих програм знову зріс інтерес до неї. Якщо набрати запит про пошук гри в Інтернет, то пошукова машина видасть декілька тисяч посилань. Тут і реклама, і різні варіанти гри, і якісні дослідження оптимальних стратегій гри і т.д. Але мало хто знає про те, що ця гра має серйозне наукове і практичне застосування, і для її аналізу можуть бути використані сучасні математичні та комп'ютерні методи. Як приклад такого додатка можна навести проблему ефективного пошуку записів у великих базах даних, які мають складною багаторівневою структурою.

Зупинимося на деяких основних правилах класичного варіанту гри. Перший гравець, гравець А, розставляє кораблі на квадратному ігровому полі з n клітин (зазвичай це поле клітин). Кораблі діляться на класи: одноклітинні, двухклеточного, трехклеточние і четирехклеточние. Гравець В на своєму полі розставляє свої кораблі. Зауважимо, що кораблі не повинні торкатися один одного. Гра полягає в тому, що гравці по черзі називають координати клітин, в яких, як вони припускають, розташовані кораблі супротивника, тобто як би роблять постріл з обраної клітці. Про попадання або промаху гравцеві повідомляється після пострілу. Гра продовжується до тих пір, поки у одного з гравців не будуть знищені всі кораблі.

На перший погляд, ця гра носить чисто імовірнісний характер, так як гравці ведуть обстріл, не знаючи розташування кораблів супротивника. Але, придбавши деякий досвід гри, можна помітити, що існують стратегії розстановки кораблів, які зменшують імовірність потрапляння в останній одноклітинний корабель. Наприклад, можна розташувати весь флот таким чином, щоб він займав мінімальне місце на ігровому полі, а один або два кораблі ставлять на останньому просторі як на малюнку 1. Пошук кораблів також можна проводити, дотримуючись певної системи, яка дозволяє найбільш швидко виявити на початку гри багатоклітинні кораблі, а потім на останньому просторі шукати одноклітинні кораблі.

Малюнок 1

Ці якісні міркування показують, що у гравців А і В існує безліч нерівнозначних різних стратегій гри, тобто може бути поставлено питання про пошук оптимальних стратегій.

Зауважимо, що все це різноманітність стратегій, як це буде показано нижче, визначається правилом, що забороняє ставити кораблі впритул, а також правилом закінчення гри.

Надалі будемо розглядати тільки односторонню гру: гравець А розставляє кораблі, а гравець В веде їх пошук.

Математичну модель гри можна будувати двома способами. Перший спосіб полягає в тому, що після кожного пострілу враховуються зміни поля гри та ймовірності виявлення кораблів. Така форма гри називається розгорнутої, а сама гра представляється багатокрокової. Складність застосування цього підходу пов'язана з необхідністю визначення ймовірностей подій, які є комбінацією великого числа елементарних подій. При збільшенні числа пострілів k кількість комбінацій зростає пропорційно k! (Факторіалі k).

Другий спосіб полягає в тому, що в якості початкового безлічі подій розглядається безліч стратегій, елементи яких представляють повну послідовність n пострілів. У цьому випадку гра стає однокрокової, тобто гравець робить вибір не однієї клітини при пострілі, а вибирає послідовність з n пострілів. Така форма гри називається нормальною. Другий підхід до побудови гри носить інтегральний характер, однак, в цьому випадку виникає проблема, пов'язана з поняттям закінчення гри.

1. Постановка завдання

Завдання полягає в розробці алгоритму, за яким комп'ютер зможе грати в «Морський бій» з максимальною якістю, і при цьому не підглядаючи розташування флоту гравця.

Додаткове і очевидне умова: при кожній новій грі незалежно від розміщення сил противника комп'ютер повинен грати по-різному, тобто його ходи повинні бути не передбачувані.

Необхідно згадати правила гри: учасники поєдинку роблять ходи по черзі, причому, якщо один з гравців потрапляє по кораблю суперника, то він отримує право наступного ходу. Якщо реалізувати пошук мети комп'ютером у вигляді окремої процедури, то треба якось навчити його запам'ятовувати результати минулих пострілів, щоб адекватно провести наступний. З цього факту випливає, що саме просте і раціональне вирішення цієї проблеми можна оформити у вигляді кінцевого автомата, найбільш точно описує послідовність дій.

Можна виділити три стани:

  1. простріл ігрового поля по випадкових координатами до попадання по кораблю, після чого перехід у другу стан;

  2. обстріл навколо підбитим осередку поля для визначення напрямку корабля (вертикальне чи горизонтальне), після чергового попадання - перехід в третій стан;

  3. розстріл корабля в отриманому напрямку до повного його знищення, після чого перехід в перший стан.

І так, вся гра зациклена на трьох основних діях: простріл, обстріл і розстріл. Всі ці дії повинні продовжуватися до тих пір, поки в однієї зі сторін не будуть знищені всі кораблі.

Простріл

На цьому етапі комп'ютер повинен зловити будь-якої з кораблів противника. Для цього він буде стріляти по довільним незайнятим клітинам поля гравця. Набагато ефективніше спочатку розправитися з великими кораблями, тому вибираючи координати для пострілу треба перевіряти, що б у цій позиції міг розміститися найбільший з решти кораблів. Процес припиняється, як тільки відбудеться влучання. Позначимо підбиту частина корабля значенням «*», а промах «~» відповідної комірки поля. Якщо у гравця залишилися тільки однопалубні кораблі, то цим попаданням корабель знищений повністю і обстрілювати його немає сенсу. В іншому випадку треба перейти до другого стану.

Обстріл

На цьому кроці завдання полягає у визначенні напрямку спійманого корабля. Для цього треба обстріляти чотири осередки (якщо вони вільні), які можуть служити продовженням. У випадку, коли всі чотири клітини обстріляні, а потрапляння не відбулося (однопалубний корабель), треба перейти до першого стану. Якщо в якийсь момент вдалося підбити ще одну палубу супротивника, то можна переходить до розстрілу даного корабля, тому що його напрямок стало відомо. Аналогічно першому стану, якщо у гравця залишилися кораблі не більше двох палуб, то цим попаданням корабель знищений повністю і треба повернутися до прострілу.

Розстріл

На попередньому кроці вдалося встановити в якому напрямку розміщений спійманий корабель. Тепер завдання полягає в його повному знищенні. Для цього треба стріляти праворуч або ліворуч (зверху чи знизу) підбитих палуб, поки не доб'ємо його повністю, після чого повернемося в стан прострілу. При цьому слід враховувати максимально можливий корабель і намагатися потрапити по четвертій палубі, коли чотирьох палубний корабель знищений, немає ніякого сенсу.

Приклад

Поле кораблів

1

1

1

1

0

0

1

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

1

0

1

0

0

0

1

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

1

0

0

0

0

1

1

0

0

0

0

1

0

1

0

0

0

0

1

1

1

Стратегія гри комп'ютера.

  1. Вибирається випадкова клітина, розглядається її значення.

  2. Якщо значення = 1 - потрапили в корабель, відзначаємо удар «*»;

  3. Якщо значення = 0 - промахнулися, відзначаємо удар «~»;

  4. Якщо значення = «*» або значення = «~», значить в цю клітку нами вже був зроблений удар, повертаємося до кроку 1.

Після того як всі кораблі розбиті, припиняємо бій. Поле розбитих кораблів

*

*

*

*

~

~

*

~

~

~

~

~

~

~

~

~

*

~

~

~

~

~

~

~

*

~

*

~

~

~

*

~

~

~

*

~

~

~

~

~

~

~

~

~

~

~

~

~

~

~

~

~

~

~

0

~

~

~

~

~

~

~

*

~

~

~

~

~

0

*

~

~

~

~

~

~

~

~

~

*

~

~

~

~

*

*

~

~

~

~

*

~

*

~

~

~

~

*

*

*

Нулями позначені ті клітини, в які ми не потрапили.

2. Математичні та алгоритмічні основи рішення задачі

Для того щоб приступити до побудови та аналізу математичної моделі гри, необхідно визначити ймовірності виявлення кораблів при різному їх розташуванні і різних системах пошуку

На полі з n клітин розташований одноклітинний корабель. Визначимо вірогідність попадання в корабель k-им пострілом, тобто його знищення.

В якості простору елементарних фіналів вибору гравця У розглянемо безліч стратегій обстрілу ігрового поля, кожна стратегія складається з n пострілів,

,

де - Номер обраної клітини, тобто розглянемо безліч всіх вибірок з n по n клітин. Очевидно, що цей простір містить елементів і всі ці стратегії рівноможливими. Кількість стратегій з успішним результатом, тобто кількість вибірок, що містять на k-му місці шукану клітку

.

Ймовірність влучення

.

Визначимо ймовірність знищення корабля за k пострілів. Ця подія полягає в тому, що корабель може бути знищений або першим пострілом, або другим і т.д., тобто сприятлива вибірка з k клітин містить шукану клітку з кораблем. Кількість сприятливих стратегій визначиться як число невпорядкованих вибірок з безлічі n - 1 клітин за k - 1 (одна клітина, зайнята кораблем не враховується при вибірці), помножене на число перестановок в самій вибірці k! і число перестановок клітин залишилися за вибіркою (n - k )!:)!. Ймовірність влучення в одноклітинний корабель за k пострілів

. (1)

Ускладнити завдання. На полі з n клітин розташований двухклеточного корабель. Визначимо ймовірність першого влучення в корабель (в одну з його клітин) пострілом з номером k. Повне число всіляких стратегій, як і в попередньому випадку, дорівнює , А число сприятливих стратегій визначається як сума сприятливих стратегій потрапляння в одну клітку і попадання в другу клітку, тобто . Вірогідність потрапляння k-им пострілом дорівнює .

Очевидно, що при обстрілі m-клітинного корабля або m одноклітинних кораблів, ймовірність потрапляння k-им пострілом дорівнює

.

Визначення ймовірності попадання в двухклеточного корабель за k пострілів, зведеться до визначення кількості стратегій, які містять шукані клітини в перших k пострілах. Число таких стратегій буде обчислюватися як наступна сума

,

де - Вибірки, що містять або першу клітку, або другу клітку, - Вибірки, що містять одночасно дві клітини. Отже

і після перетворень отримаємо

. (2)

Зауважимо, що аналогічним чином можна визначити ймовірність попадання за k пострілів в корабель з m клітин. Завдання попадання за k пострілів у багатоклітинний корабель хоча б один раз є завданням пошуку корабля. Очевидно, що якщо врахувати геометрію корабля, то можна запропонувати систему його пошуку, при якій ймовірність виявлення стає вище. Дійсно, при пошуку двухклеточного корабля можна розглянути підмножина всіх стратегій, що містять обстріл, наприклад, клітин тільки з парними або з непарними номерами. Пошук двухклеточного корабля зведеться до пошуку одноклітинного корабля на цьому підмножині. Вважаючи n парних, для оптимальної ймовірності попадання за k пострілів отримаємо

. (3)

Знайдене значення ймовірності більше вірогідності, отриманої вище

,

при всіх значеннях .

Оптимальна стратегія пошуку трехклеточного і четирехклеточного корабля може бути отримана аналогічним чином.

Ймовірність влучення в грі «Морський бій»

Всього клітин 100

а) ймовірність потрапити в який-небудь корабель дорівнює ;

б) імовірність потрапити в чотирипалубних дорівнює ;

в) ймовірність потрапити в однопалубний дорівнює ;

Всього кораблів 10, не однопалубних 6, «клітинок» 16.

а) ймовірність потрапити в чотирипалубних дорівнює ;

б) імовірність потрапити в трипалубний дорівнює ;

в) ймовірність потрапити в двопалубний дорівнює .

3. Функціональна модель вирішення задачі

Функціональна модель вирішення завдання представлені на малюнку 2.

Рисунок 2 - Функціональна модель вирішення задачі для функції BLOW

4. Програмна реалізація рішення задачі

; Відкриваємо файл для читання

(Setq input_stream (open «D: \ \ field.txt»: direction: input))

; Зчитуємо поле противника

(Setq field (read input_stream))

; Закриваємо файл

(Close input_stream)

; Кількість кораблів

(Setq user_ship 10)

; Вбиваємо корабель

(Defun set_missing_comp (lst ij ip jp)

(Setq k (if (> = (- i 1) 0) (- i 1) i))

(Setq l (if (> = (- j 1) 0) (- j 1) j))

(Loop

(Do

()

((Or (> k (+ i 1)) (> = k 10)))

(Do

()

((Or (> l (+ j 1)) (> = l 10)))

(If (eql (nth l (nth k lst)) 1)

(Progn

(Setq k 10)

(Return t)

)

)

(Setq l (+ l 1))

)

(Setq k (+ k 1))

)

(Return nil)

)

(Setq k (if (> = (- i 1) 0) (- i 1) i))

(Setq l (if (> = (- j 1) 0) (- j 1) j))

(Loop

(Do

()

((Or (> k (+ i 1)) (> = k 10)))

(Do

()

((Or (> l (+ j 1)) (> = l 10)))

(If (not (eql (nth l (nth k lst)) '*)) (setf (nth l (nth k lst))' ~))

(Setq l (+ l 1))

)

(Setq k (+ k 1))

)

(Return nil)

)

t

)

; Крокуємо у напрямку «хреста»

(Defun set_missing (lst ij ip jp)

(If (> = (- i 1) 0)

(If (and (/ = (- i 1) ip) (eql (nth j (nth (- i 1) lst)) 1))

(Set_missing lst (- i 1) jij)

)

)

(If (> = (- j 1) 0)

(If (and (/ = (- j 1) jp) (eql (nth (- j 1) (nth i lst)) 1))

(Set_missing lst i (- j 1) ij)

)

)

(If (<(+ i 1) 10)

(If (and (/ = (+ i 1) ip) (eql (nth j (nth (+ i 1) lst)) 1))

(Set_missing lst (+ i 1) jij)

)

)

(If (<(+ j 1) 10)

(If (and (/ = (+ j 1) jp) (eql (nth (+ j 1) (nth i lst)) 1))

(Set_missing lst i (+ j 1) ij)

)

)

(If (eql (nth j (nth i lst)) 1) (setf (nth j (nth i lst)) '*))

)

; Функція, що реалізує удар по полю

(Defun blow (lst)

; Вибираємо випадкову клітку

(Setq i (random 10))

(Setq j (random 10))

(Setq n (nth j (nth i lst)))

(Cond

((Eql n 1)

(Progn

; Значення в клітці = 1

; Вбиваємо корабель

(Set_missing lst ijij)

(Set_missing_comp lst ijij)

(Setq user_ship (- user_ship 1))

(If (/ = user_ship 0) (blow lst))

)

)

((Eql n 0)

(Progn

; Значення в клітці 0

; Промахнулися

(Setf (nth j (nth i lst)) '~)

(Blow lst)

)

)

; Вже були в цій клітці - вибираємо іншу

((Or (equal n '*) (equal n' ~)) (blow lst))

)

lst

)

; Вбиваємо противника!

(Blow field)

; Файл для запису

(Setq output_stream (open «D: \ \ destroy_field.txt»: direction: output))

; Записуємо побите поле противника

(Print field output_stream)

; Закриваємо файл

(Close output_stream)

5. Приклад виконання програми

Приклад 1.

Рисунок 3 - Поле кораблів

Рисунок 4 - Розстріляне полі кораблів

Приклад 2.

Малюнок 5 - Поле кораблів

Малюнок 6 - Розстріляне полі кораблів

Приклад 3.

Малюнок 7 - Поле кораблів

Малюнок 8 - Розстріляне полі кораблів

Висновок

Наведений приклад аналізу гри «Морський бій» показує можливість використання логічних ігор для поглибленого вивчення таких розділів математики, як комбінаторика, теорія множин і теорія ймовірностей. Зауважимо, що вивчення навіть найпростіших ігрових ситуацій дозволяє сформулювати проблеми, які представляють інтерес для сучасної інформатики та теорії пошуку.

Підсумком роботи можна вважати створену функціональну модель реалізації стратегії гри «Морський бій». Створена функціональна модель і її програмна реалізація можуть служити органічною частиною вирішення більш складних завдань.

Список використаних джерел та літератури

  1. Бронштейн, І.М. Довідник з математики для інженерів і учнів втузів [Текст] / І.М. Бронштейн, К.А. Семендяев. - М.: Наука, 2007. - 708 с.

  2. Кремер, Н.Ш. Вища математика для економістів: підручник для студентів вузів. [Текст] / Н.Ш. Кремер, 3-е видання - М.: ЮНИТИ-ДАНА, 2006. C. 412.

  3. Петросян, Л.А. Ігри пошуку [Електронний ресурс] / Л.А. Петросян, О.Ю. Гарнаєв. - М.: СПбДУ, 1992. С. 314.

  4. Реалізація гри «Морський бій» [Електронний ресурс] - Режим доступу: http://aka-alex.narod.ru/index.htm

  5. Семакін, І.Г. Основи програмування. [Текст] / І.Г. Семакін, А.П. Шестаков. - М.: Світ, 2006. C. 346.

  6. Сіманков, В.С. Основи функціонального програмування [Текст] / В.С. Сіманков, Т.Т. Зангієв, І.В. Зайцев. - Краснодар: КубГТУ, 2002. - 160 с.

  7. Степанов, П.А. Функціональне програмування мовою Lisp. [Електронний ресурс] / П.А. Степанов, А.В. Бржезовскій. - М.: ГУАП, 2003. С. 79.

  8. Хювенен Е. Світ Ліспу [Текст] / Е. Хювенен, Й. Сеппянен. - М.: Світ, 1990. - 460 с.

    Додати в блог або на сайт

    Цей текст може містити помилки.

    Програмування, комп'ютери, інформатика і кібернетика | Курсова
    90.5кб. | скачати

    Схожі роботи:
    Ютландська морський бій
    Створення ігрової програми Морський бій
    Робота з персональним комп`ютером
    Основи роботи з комп`ютером
    Як вижити працюючи з комп`ютером
    Правила роботи учнів з комп`ютером
    Заходи безпеки при роботі за комп`ютером
    Техніка безпеки при роботі за комп`ютером
    UNIX та Internet робота з віддаленим комп ютером
© Усі права захищені
написати до нас